#include "CountingSort.h"
void show(std::vector<TYPE> &nums){
    std::cout<<"nums:";
    for (int i = 0; i < nums.size(); ++i) {
        std::cout<<nums[i]<<",";
    }std::cout<<std::endl;
}

void CountingSort(std::vector<TYPE> &nums,bool miniToMax)
{
    int max = nums[0];
    int min = nums[0];

    for (int i = 0; i < nums.size(); ++i) {//找出待排序的数组中最大和最小的元素
        if(max < nums[i]){
            max = nums[i];
        }
        if(min > nums[i]){
            min = nums[i];
        }
    }

    int offset = (max - min) + 1;
    std::cout<<"offset:"<<offset<<",max:"<<max<<",min:"<<min<<std::endl;
    std::vector<int> nums2;
    nums2.resize(offset,0);

    for (int i = 0; i < nums.size(); ++i) {//统计数组中每个值为i的元素出现的次数，存入数组C的第i项
        int j = (nums[i]);
        nums2[j]++;
    }
    show(nums2);
    int k = 0;
    for (int i = 0; i < nums2.size(); ++i) {
        int cnt = nums2[i];
        for (int j = 0; j < cnt; ++j) {
            nums[k] = i;
            k++;
        }
    }
}


int main(){
    std::vector<int> nums = {1,3,5,7,2,6,4,8,9,2,8,7,6,0,3,5,9,4,1,0};
    show(nums);
    CountingSort(nums,true);
    show(nums);
//    std::vector<int> nums1 = {1,3,5,7,2,6,4,8,9,2,8,7,6,0,3,5,9,4,1,0};
//    show(nums1);
//    CountingSort(nums1, false);
//    show(nums1);
    return 0;
}